package datastructure.search;

/**
 * Description：进行插入排序时，折半查找，查找插入位置，返回0和最后一个元素下标的下一个位置之间的数字。
 * Author: zhangc
 * Date：2017/7/26 10:23
 */
public class BinarySearchInsertIndex {

    public static <T extends Comparable<? super T>> int findIndexInsert(T[] array, int low, int high, T key) {
        if (array[ low ].compareTo(key) > 0)
            return low;
        else if (array[ high ].compareTo(key) <= 0)
            return ++high;
        else {
            int mid = (low + high) >> 1;
            if (array[ mid ].compareTo(key) > 0)
                return findIndexInsert(array, low, mid - 1, key);
            else
                return findIndexInsert(array, mid + 1, high, key);
        }
    }

}
